package com.cqs.leetcode.backtrack;

import java.util.*;

/**
 * @author lixqw
 * @date 2020/9/9
 */
public class CombinationSum39 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> list = new ArrayList<>();
        combination(candidates, target, 0, new ArrayList<>(), list);
        return list;
    }

    private void combination(int[] candidates, int target, int level, List<Integer> tmp, List<List<Integer>> result) {
        //递归出口
        if (target == 0) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        int pre = -1;
        for (int i = level; i < candidates.length; i++) {
            int candidate = candidates[i];
            //减枝
            if (candidate> target) return;
            //去重
            if (candidate == pre) continue;
            pre = candidate;
            tmp.add(candidate);
            combination(candidates, target - candidate, i, tmp, result);
            //回溯
            tmp.remove(tmp.size() - 1);
        }
    }

    public static void main(String[] args) {
        Map<int[],Integer> tests = new LinkedHashMap<>();
        tests.put(new int[]{2,3,5},8);
        tests.put(new int[]{2,3,6,7},7);
        CombinationSum39 com = new CombinationSum39();
        tests.forEach((candidates,target)->{
            List<List<Integer>> lists = com.combinationSum(candidates, target);
            System.out.println(lists);
        });
    }
}
